package LimitedTimeGame.Day_0214;

/**
 * @author zxc
 * @date 2023/02/14 15:10
 **/

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 题目 ：在每个树行中找寻最大值
 * 题目详述 ：
 * 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
 *
 * 提示：
 * 二叉树的节点个数的范围是 [0,104]
 * -231 <= Node.val <= 231 - 1
 *
 */
public class LargestValues {
    /**
     * 思路 ：
     * 使用树的广度遍历算法
     * ===》
     * （1）即，通过两个栈 stack 和 temp，stack来存储当前层需要遍历的所有树节点;同时，temp用来存储下一层需要遍历的所有树节点;
     * （2）同时，在对于二叉树每一层的所有树节点遍历过程中，求取当前层所有树节点的最大值;
     *
     * 或者
     * 使用一个栈，但是需要一个变量，来记录下一层需要遍历的树节点数目;
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> temp = new Stack<>();
        // 特殊情况 ：root根节点为null;
        if(root == null){
            return result;
        }
        // 若是根节点不为 null的话，即直接将其压入栈中，作为二叉树的第一层;
        stack.push(root);
        // 遍历政客二叉树
        while(!stack.isEmpty()){
            int max = Integer.MIN_VALUE;
            // 遍历二叉树当前层的所有树节点
            while(!stack.isEmpty()){
                TreeNode popTreeNode = stack.pop();
                System.out.println(popTreeNode.val);
                max = Math.max(max , popTreeNode.val);
                if(popTreeNode.left != null){
                    temp.push(popTreeNode.left);
                }
                if (popTreeNode.right != null){
                    temp.push(popTreeNode.right);
                }
            }
            // temp所保存的所有树节点都赋值给stack;
            stack = temp;
            temp = new Stack<>();
            result.add(max);
        }
        return result;
    }
    // TreeNode树节点类;
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
}
